package com.zhugang.september;

import java.util.HashMap;
import java.util.Map;

/**
 * @program algorithms
 * @description: test
 * @author: chanzhugang
 * @create: 2021/09/21 00:21
 */
public class Fibonacci {

    /**
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     * 注意：给定 n 是一个正整数。
     */

    static Map<Integer, Integer> cache = new HashMap<>();

    public static void main(String[] args) {
        int n = 6;
        int result = fibonacci1(n);
        System.out.println(result);

        System.out.println("测试commit追加");
    }

    /**
     * 时间复杂度高：leetcode提交超时
     */
    public static int fibonacci(int n) {
        if (n <= 2) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    /**
     * 添加全局缓存
     */
    public static int fibonacci1(int n) {
        if (n <= 2) {
            return n;
        }
        if (cache.containsKey(n)) {
            return cache.get(n);
        }
        int result = fibonacci1(n - 1) + fibonacci1(n - 2);
        cache.put(n, result);
        return result;
    }

    /**
     * 动态规划： 滚动数组思想
     */
    public static int fibonacci2(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 0; i < n; i++) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;

    }
}